#include<stdlib.h>
#include "array_and_file.c"
#include "swap.c"
#pragma once


/*PROTOTYPES*/
void quick_sort_main (int *array, int file_size, char *unsorted_input_file, char *sorted_output_file);
void quick_sort (int *array, int first, int last);

void quick_sort_main (int *array, int file_size, char *unsorted_input_file, char *sorted_output_file)
{
    /*clock_t start, now;
	double file_read_time;*/

    read_file_into_array (array, file_size, unsorted_input_file);
    quick_sort (array, 0, file_size - 1);
    write_array_to_file (array, file_size, sorted_output_file);
}



//This implementation uses a random pivot.
/*void quick_sort (int *array, int first, int last)
{
    int selector1, selector2, pivot, pivot_index, size;

    size = last - first + 1;

    if (size > 1) {     //If size <= 1, do nothing.
        pivot_index = first + (rand () % size);        //Choose a pivot randomly between first and last.
        pivot = array[pivot_index];

        selector1 = first;
        selector2 = last;

        //Create left and right partitions.
        while (selector1 < selector2) {      //Process untill both indices cross.
            while (array[selector1] < pivot) selector1++;        //Increment selector1 from 0 until it points to a value >= pivot.
            while (array[selector2] > pivot) selector2--;        //Decrement selector2 from 'last' until it points to a value <= pivot.
            if (selector1 < selector2) swap (&array[selector1], &array[selector2]);        //Once selector1 and selector2 point to the appropriate values, we swap them.
        }

    //The pivot is in place. We now recursively sort the left and right partitions.
    quick_sort (array, first, selector1 - 1);
    quick_sort (array, selector1 + 1, last);
    }
}
*/



void quick_sort(int *x,int first,int last){
    int pivot,j,temp,i;

     if(first<last){
         pivot=first;
         i=first;
         j=last;

         while(i<j){
             while(x[i]<=x[pivot]&&i<last)
                 i++;
             while(x[j]>x[pivot])
                 j--;
             if(i<j){
                 temp=x[i];
                  x[i]=x[j];
                  x[j]=temp;
             }
         }

         temp=x[pivot];
         x[pivot]=x[j];
         x[j]=temp;
         quick_sort(x,first,j-1);
         quick_sort(x,j+1,last);

    }
}

